package leetcode.editor.cn.dsa09_doublequeue;
//给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数

import java.util.Arrays;

public class RotateArray189_1 {
    public static void main(String[] args) {
        Solution solution = new RotateArray189_1().new Solution();
        int[] arr = {1,2,3,4,5,6,7}; int k = 3;
        solution.rotate(arr, k);
        System.out.println(Arrays.toString(arr));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 在原数组原地移动首先想到的最好做法是：原地交换(翻转)
         * 找规律：
         *     对于数组: [1,2,3,4,5,6,7]
         *     旋转1步: [7, 1,2,3,4,5,6]
         *     旋转2步: [6,7, 1,2,3,4,5]
         *     旋转3步: [5,6,7, 1,2,3,4]
         *     我们把旋转后的数组分为两半，左边是旋转元素的个数k，右边是剩下的元素，即len-k
         *     你会发现左右两边数据都保持着原数组的顺序，只是把一部分数据提到了数组的前面，
         *     因此我们可以对左右两边数据进行翻转，翻转后的数据肯定是原数组的倒序序列
         *     旋转k次左右数据翻转后：[7,6,5,4,3,2,1]
         *
         * 逆序思维：
         *     题目要求求出旋转k次后的数组序列(以3次为例)，按照前面的规律，我们逆序思维思考
         * 步骤如下：
         *     1.把整个数组进行翻转，得到 [7,6,5,4,3,2,1]
         *     2.求出真正要旋转的次数c，k % nums.length = 3
         *       当k超过数组长度时，例如旋转8次，其实是旋转1次，因此需要取模
         *     3.按照次数c将数组分为两半，即[7,6,5]和[4,3,2,1](逻辑分组)
         *       分别翻转这两个子序列，得到 [5,6,7,1,2,3,4]
         *
         * @param nums
         * @param k
         */
        public void rotate(int[] nums, int k) {
            int len = nums.length;
            // 1.把整个数组进行翻转
            reverse(nums, 0, len - 1);
            // 2.求出真正要旋转的次数
            k = k % len;
            // 3.按照次数c将数组分为两半，分别翻转这两个子序列
            reverse(nums, 0, k - 1);
            reverse(nums, k, len - 1);

        }

        /**
         * 翻转数组指定索引范围内的元素
         * @param nums 待翻转数组
         * @param start 开始索引
         * @param end 结束索引
         */
        public void reverse (int[] nums, int start, int end) {
            while (start < end) { // 循环结束条件是 start >= end
                // 取两端元素进行交换
                int temp = nums[start];
                nums[start++] = nums[end];
                nums[end--] = temp;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}